#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

class Solution {
public:
    string addStrings(string num1, string num2) {

        string s;

        reverse(num1.begin(), num1.end());

        reverse(num2.begin(), num2.end());

        int i1 = 0, i2 = 0, next = 0;
        while (i1 < num1.size() || i2 < num2.size())
        {

            int x1 = i1 < num1.size() ? num1[i1++] - '0' : 0;

            int x2 = i2 < num2.size() ? num2[i2++] - '0' : 0;



            s += (x1 + x2 + next) % 10 + '0';

            next = (x1 + x2 + next) / 10;

        }
        if (next == 1)
        {
            s += '1';
        }
        reverse(s.begin(), s.end());
        return s;

    }
    string multiply(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1, next = 0, i = 0;
        string* s = new string[end2+1] ;
        if (num1[0] == '0' || num2[0] == '0')
        {
            return "0";
        }
        while (end2 >= 0)
        {
            next = 0;
            end1 = num1.size() - 1;
            for (int j = 0; j < i; j++)
            {
                    s[i] += '0';
            }
            while (end1 >= 0)
            {
                int x1 = num1[end1--] - '0';
                int x2 = num2[end2] - '0';

                s[i] += (x1 * x2 + next) % 10 + '0';
                next = (x1 * x2 + next) / 10;
            }
            if (next > 0)
            {
                s[i] += next + '0';
            }
            end2--;
            i++;
        }
        string ret;
        for (int n = 0; n < num2.size(); n++)
        {
            reverse(s[n].begin(), s[n].end());
            ret = addStrings(ret, s[n]);
        }


        return ret;
    }
};

void Testmultiply()
{
    Solution s;
    cout << s.multiply("9133", "0") << endl;
    cout << s.multiply("9", "99") << endl;
    cout << s.multiply("123", "456")<<endl;
    cout << s.multiply("2", "3")<<endl;
}

//class Solution {
//public:
//    bool isPalindrome(string s) {
//        int i = 0, end = s.size();
//        string str;
//        while (i < end)
//        {
//            char ch = s[i++];
//            if (ch >= 'A' && ch <= 'Z')
//            {
//                str += ch + 32;
//            }
//            else if (ch >= 'a' && ch <= 'z')
//            {
//                str += ch;
//            }
//            else if (ch >= '0' && ch <= '9')
//            {
//                str += ch;
//            }
//        }
//        int left = 0, right = str.size() - 1;
//        while (left < right)
//        {
//            if (str[left++] != str[right--])
//                return false;
//        }
//        return true;
//    }
//};

//void TsetisPalindrome() 
//{
//    Solution s;
//    cout << s.isPalindrome("A man, a plan, a canal: Panama") << endl;
//    cout << s.isPalindrome("0P") << endl;
//}

//class Solution {
//public:
//    void reverseString(vector<char>& s) {
//        int left = 0, right = s.size() - 1;
//        while (left < right)
//        {
//            swap(s[left++], s[right--]);
//        }
//    }
//};
//
//
//class Solution {
//public:
//    string addStrings(string num1, string num2) {
//        string s;
//        reverse(num1.begin(), num1.end());
//        reverse(num2.begin(),num2.end());
//        int i1 = 0,i2 = 0, next = 0;
//
//        
//        while (i1 < num1.size() || i2 < num2.size())
//        {
//            int x1 = i1 < num1.size() ? num1[i1++] - '0' : 0;
//            int x2 = i2 < num2.size() ? num2[i2++] - '0' : 0;
//
//            s += (x1+x2+next)% 10+'0';
//            next = (x1 + x2 + next) / 10;
//        }
//
//        if (next == 1)
//        {
//            s += '1';
//        }
//        reverse(s.begin(), s.end());
//        return s;
//    }
//};

int main()
{
    //TsetisPalindrome();
    Testmultiply();

	return 0;
}